//
// Created by mazaiting on 2024/4/27.
//

#include <bits/stdc++.h>

using namespace std;
const int MaxSize = 100;        //栈中最多元素个数

template<typename T>
struct LinkNode                //链栈结点类型
{
    T data;                    //数据域
    LinkNode *next;                //指针域
    LinkNode() : next(NULL) {}            //构造函数
    explicit LinkNode(T d) : data(d), next(nullptr) {}    //重载构造函数
};

template<typename T>
class STACK2                    //链栈类模板
{
public:
    LinkNode<T> *rear;                //链栈尾结点指针
    STACK2() : rear(nullptr) {}            //构造函数
    ~STACK2()                    //析构函数
    {
        if (rear == nullptr) return;            //空链表直接返回
        LinkNode<T> *pre = rear, *p = pre->next;
        while (p != rear) {
            delete pre;
            pre = p;
            p = p->next;            //pre、p同步后移
        }
        delete pre;
    }

    bool empty()                //判栈空算法
    {
        return rear == nullptr;
    }

    bool push(T e)                  //进栈算法
    {
        auto *p = new LinkNode<T>(e); //新建结点p
        if (empty())              //栈为空的情况
        {
            rear = p;
            rear->next = rear;
        } else                      //栈不空的情况
        {
            p->next = rear->next;          //将结点p插入到结点rear之后
            rear->next = p;
        }
        return true;
    }

    bool pop(T &e)                //出栈算法
    {
        LinkNode<T> *p;
        if (empty()) return false;    //栈空的情况
        if (rear->next == rear)        //栈中只有一个结点的情况
        {
            p = rear;
            rear = nullptr;
        } else                    //栈中有2个及以上结点的情况
        {
            p = rear->next;
            rear->next = p->next;
        }
        e = p->data;
        delete p;                //释放结点p
        return true;
    }

    bool gettop(T &e)            //取栈顶元素
    {
        if (empty()) return false;    //栈空的情况
        e = rear->next->data;
        return true;
    }

    T Getbottom()            //取栈底元素
    {
        return rear->data;
    }
};

int main() {
    int e;
    STACK2<int> st;
    cout << "1到5进栈" << endl;
    for (int i = 1; i <= 5; i++)
        st.push(i);
    cout << "栈底元素: " << st.Getbottom() << endl;
    st.pop(e);
    cout << "出栈元素" << e << endl;
    st.pop(e);
    cout << "出栈元素" << e << endl;
    cout << "栈底元素: " << st.Getbottom() << endl;
    return 0;
}


